给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。
有效的 IP 地址 正好由四个整数（每个整数位于 0 到 255之间组成，且不能含有前导 0），整数之间用 '.' 分隔。
例如："0.1.2.201" 和 "192.168.1.1" 是 有效的 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效的 IP 地址。
示例 1：
输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]
示例 2：
输入：s = "0000"
输出：["0.0.0.0"]
示例 3：
输入：s = "1111"
输出：["1.1.1.1"]
示例 4：
输入：s = "010010"
输出：["0.10.0.10","0.100.1.0"]
示例 5：
输入：s = "101023"
输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
提示：
- 0 <= s.length <= 3000
- s 仅由数字组成
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/restore-ip-addresses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路及分析
题目分析
-
ip地址最长12位(255.255.255.255)，最短4位(0.0.0.0) -
ip地址可以看成是4段小字符串由.连接成的长字符串 -
每个小字符串的长度范围是
0 ～ 3 -
小字符串长度大于
1时，首个字符不能是0
算法分析
使用『回溯算法』解决此题，只要涉及到『回溯算法』，一定要画出决策树，可以让我们直观了解如何进行剪枝。
图片来源：回溯算法（画图分析剪枝条件）
1、一开始，字符串的长度小于 4 或者大于 12 ，一定不能拼凑出合法的 ip 地址（这一点可以一般化到中间结点的判断中，以产生剪枝行为）；
2、每一个结点可以选择截取的方法只有 3 种：截 1 位、截 2 位、截 3 位，因此每一个结点可以生长出的分支最多只有 3 条分支；
代码1
from typing import List
class Solution:
def restoreIpAddresses(self, s: str) -> List[str]:
size = len(s)
# 字符串长度小于最小ip地址长度或大于最长ip地址长度
# 直接返回[]
if size < 4 or size > 12:
return []
path = []
res = []
def dfs(s, size, path, res, left, split_time):
# left遍历到最后以及分割次数为4，则表示找到一个结果
if left == size:
if split_time == 4:
res.append('.'.join(path))
return
# 如果left之后的字符数超过最大剩余数 或 小于最小剩余数，均可剪枝提前退出
elif size - left > (4 - split_time) * 3 or size - left < 4 - split_time:
return
for inx in range(left, size):
# 获取当前字符串
c = s[left:inx+1]
# 当长度大于1时，判断其首字符是不是0,
# c的整数型必须小于255
if len(c) > 1 and c[0] == '0' or int(c) > 255:
return
# 选择
path.append(c)
# 进行下一层继续选择
dfs(s, size, path, res, inx+1, split_time+1)
# 回溯
path.pop()
dfs(s, size, path, res, 0, 0)
return res